<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8"> <meta name="viewport" content="width=device-width">
    <title>独立集问题的各种总结</title>
    <meta name="viewport" content="width=device-width,initial-scale=1, shrink-to-fit=no">
    <!-- Bootstrap CSS -->
    <link rel="stylesheet"
          href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/css/bootstrap.min.css"
          integrity="sha384-9aIt2nRpC12Uk9gS9baDl411NQApFmC26EwAOH8WgZl5MYYxFfc+NcPb1dKGj7Sk"
          crossorigin="anonymous">
    <link rel="stylesheet"
          href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/androidstudio.min.css">
<!--    <link rel="stylesheet" href="/web_template_css.css">-->
    <!-- this is highlight.js -->
    <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
    <script id="MathJax-script" async
            src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
    </script>
    <script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.slim.min.js"
    integrity="sha384-DfXdz2htPH0lsSSs5nCTpuj/zy4C+OGpamoFVy38MVBnE+IbbVYUew+OrCXaRkfj" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.0/dist/umd/popper.min.js"
    integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/js/bootstrap.min.js"
    integrity="sha384-OgVRvuATP1z7JjHLkuOU7Xw704+h835Lr+6QL9UvYjZE3Ipu6Tp75j7Bh/kR0JKI" crossorigin="anonymous"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
    <style>
      img{
        display: block;
        height: auto;
        max-width: 100%;
      }
    </style>
  </head>
  <body>
    <nav class="navbar navbar-expand-lg navbar-light bg-light">
        <a class="navbar-brand" href="#">kvrmnks</a>
        <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarNav" aria-controls="navbarNav" aria-expanded="false" aria-label="Toggle navigation">
          <span class="navbar-toggler-icon"></span>
        </button>
        <div class="collapse navbar-collapse" id="navbarNav">
          <ul class="navbar-nav">
            <li class="nav-item active">
              <a class="nav-link" href="./../../../../../index.html" target="_self">Home <span class="sr-only">(current)</span></a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../blog.html">Blog</a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../about.html">About</a>
            </li>
          </ul>
        </div>
      </nav>



    <div class='container'>
      <h2>顶点覆盖问题的各种总结</h2>

<h3>顶点覆盖问题</h3>

<p>有一张图\(G=&lt;V,E&gt;\)，找到一个\(V\)的一个子集\(S\)，\(s.t. \forall a,b\in E,a\in S\)或\(b\in S\)。</p>

<p>判定性的问题是，给定一个正整数\(L\)，问是否能存在一个\(S\)，使得\(|S| \leq L\).</p>

<p>最优化的问题是，找到一个\(S\), 使得\(|S|\)最小。</p>

<h3>复杂度分析</h3>

<h4>该问题和独立集问题一样难</h4>

<p>首先证明顶点覆盖不比独立集简单，对于一张图，若求出了这张图的最大独立集\(T\), 取\(S = V-T\), 我们断言\(S\)便是这张图的最小顶点覆盖。</p>

<p>首先证明\(S\)是一个顶点覆盖，采用反证法，若是存在一条边\(ab\)没有被覆盖，由构造过程可以得到\(a,b\in T\), 则与\(T\)是独立集矛盾，于是\(S\)是一个顶点覆盖。</p>

<p>再证明\(S\)是一个最小的顶点覆盖，依旧采用反证法，假设\(S\)并不是一个最小的顶点覆盖，那么一定存在一个点\(x\)可以去掉，使得\(S-\{x\}\)还是一个顶点覆盖，也就是说对于\(\forall ax\in E\)，\(a\)一定在\(S\)中，则\(a\)一定不在\(T\)中, 于是在\(T\)中加入\(x\)依旧是一个独立集, 与\(T\)是最大独立集相矛盾, 于是\(S\)一定是一个最小顶点覆盖.</p>

<p>并且独立集问题不比顶点覆盖问题简单, 假设已知最小顶点覆盖\(S\), 则取\(T = V-S\), 我们断言\(T\)是最大独立集, 证明比较简单, 不再赘述.</p>

<h4>该问题是NP-Complete问题</h4>

<p>通过\(Cook&#39;s\)  \(theorem\), 我们首先知道\(SAT \in NP-Complete\).</p>

<p>可以通过多项式归约链推导得到\(VC\)即\(Vertex\quad cover\), \(VC \in NP-Complete\)</p>

<p>这里暂时不给出证明, 但愿不会咕(</p>

<p>仅仅给出推导链</p>

<p>\(SAT \propto 3SAT \propto VC\)</p>

<h3>二分图下的情况</h3>

<p>konig 柯尼希定理 暂时没啥想法, 路子是对的, 继续想想.</p>

<p>总之在这种情况下并不是\(NP\)问题，可以通过网络流方法在多项式时间内得到解。</p>

<h3>一般情况下</h3>

<p>在一般情况下只能寻找近似算法。</p>

<h4>度数贪心</h4>

<p>一种比较简单的贪心策略是通过度数从大到小进行贪心，这种算法的近似度上界比较难以确定，但是可以比较容易地构造出一个近似度的下界。</p>

<p><img src="image-20201103193010767.png" alt="image-20201103193010767" style="zoom:33%;" /></p>

<p>在这张图上这样的贪心做法仅仅得到\(\Omega(\log{n})\)的近似度。</p>

<h4>另一种简单贪心</h4>

<p>考虑以任意顺序枚举每一条边，如果这条边没被覆盖，则选择这一条边的两个点。</p>

<p>这个简单的做法可以得到近似度为\(2\)优秀效果。</p>

<h4>加权下的顶点覆盖问题</h4>

<p>不妨假设选择第\(i\)个点的代价为\(w_{i}\), 令\(x_{i} \in \{0,1\}\)表示是否选择第\(i\)个点。</p>

<p>问题便是最小化\(\large\sum_{i}^{n}w_{i}x_{i}\)</p>

<p>约束条件为\(\sum_{ij\in E}x_{i}+x_{j}\geq 1\)</p>

<p>考虑直接将这个形式进行松弛，即令\(x_{i}\geq 0\)</p>

<p>假设现在得到的解为\(S\)</p>

<p>那么根据线性规划松弛的原理，一定有\(S \leq OPT\)</p>

<p>下面进行取整来判断如何根据线性规划得到的解来构造出原问题的解。</p>

<p>如果\(x_{i} \geq \frac{1}{2}\)则选择\(i\)点。</p>

<p>这样显然得到的点列是一个顶点覆盖。</p>

<p>下面来考虑如何计算这个做法的近似度</p>

<p>根据\[x_{i}\geq \frac{1}{2}\]</p>

<p>有\[w_{i}x_{i}\geq \frac{w_{i}}{2}\]</p>

<p>于是有\[\sum_{i}^{n}w_{i}x_{i}\geq \sum_{i}^{n}\frac{w_{i}}{2}\]</p>

<p>\[\sum_{i}^{n} \frac{w_{i}*x^{&#39;}_{i}}{2} \leq \sum_{i}^{n}w_{i}\hat{x{i}} \leq \sum_{i}^{n}w_{i}x_{i} \leq OPT\]</p>

<p>于是有\(\frac{S}{OPT} \leq 2\)</p>

<h4>加权形式下的原始对偶算法</h4>

<p>不妨假设选择第\(i\)个点的代价为\(w_{i}\), 令\(x_{i} \in \{0,1\}\)表示是否选择第\(i\)个点。</p>

<p>问题便是最小化\(\large\sum_{i}^{n}w_{i}x_{i}\)</p>

<p>约束条件为\(\sum_{ij\in E}x_{i}+x_{j}\geq 1\)</p>

<p>考虑直接将这个形式进行松弛，即令\(x_{i}\geq 0\)</p>

<p>依旧是一开始形式的线性规划。</p>

<p>现在将这个线性规划对偶。</p>

<p>即最大化\(\sum_{i}^{n}y_{i}\)</p>

<p>约束条件为\(\sum y_{j} \leq w_{i}\)</p>

<p>则\(y_{i}\)还可以增加，使得某个不等式收紧，则得到最小的增加量\(y_{i}\)</p>

<p>更新整个过程。</p>

<p>取那些取到等号的\(i\)，构成变量。</p>

<p>可以发现当\(w_{i}=1\)的时候，整个过程等价于一开始的贪心算法。</p>

<p>下面证明这个算法的近似度。</p>

<p>首先根据对偶的性质有\(\sum y_{i} \leq OPT\)</p>

<p>\(2\sum{y} \geq \sum w\)</p>

<p>于是近似度为\(2\)</p>


    </div>
    <script>
      hljs.initHighlightingOnLoad()
    </script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlightjs-line-numbers.js/2.5.0/highlightjs-line-numbers.min.js"></script>
  <script>
      hljs.initHighlightingOnLoad();
      hljs.initLineNumbersOnLoad();
  </script>
  </body>
</html>